package leetcode;


import java.util.Collection;
import java.util.Collections;
import java.util.PriorityQueue;

//295. 数据流的中位数
public class MedianFinder {

    //维护两个优先队列，各保存一半的数，pq1保存最大的一半，且队首保存此队列中最新的值。pq2保存剩下的一半，且队首保存最大的值
    PriorityQueue<Integer>pq1;
    PriorityQueue<Integer>pq2;
    int cnt; //记录元素个数


    public MedianFinder() {
        pq1 = new PriorityQueue<>(); //小根
        pq2 = new PriorityQueue<>(Collections.reverseOrder());//大根
        this.cnt = 0;
    }

    public void addNum(int num) { //
        cnt++;
        if (pq1.isEmpty() || num >= pq1.peek()) {
            pq1.offer(num);
        }else {
            pq2.offer(num);
        }
        int pqSize = cnt / 2 + cnt % 2;
        while (pq1.size() > pqSize) {
            pq2.offer(pq1.poll());
        }
        pqSize = cnt - pqSize;
        while (pq2.size() > pqSize) {
            pq1.offer(pq2.poll());
        }
    }

    public double findMedian() {
        int sum = pq1.peek();
        if (cnt % 2 == 0) {
            sum += pq2.peek();
            return sum / 2.0;
        }
        return sum;
    }


    public static void main(String[] args) {
        MedianFinder m = new MedianFinder();
        m.addNum(-1);
        m.addNum(-2);
        m.addNum(-3);
        System.out.println(m.findMedian());
        m.addNum(-4);
        System.out.println(m.findMedian());
        m.addNum(-5);
        System.out.println(m.findMedian());
    }
}
